package leetcode;

public class ShortestPalidrome {

	public String shortestPalindrome(String s) {
		if (s == null || s.length() <= 0) {
			return s;
		}
		int length = s.length();
		int i;
		for (i = length; i >= 1; i--) {
			// 显然每次这样判断太耗时了
			if (isPalidrome(s.substring(0, i))) {
				break;
			}
		}
		StringBuilder builder = new StringBuilder();
		for (int j = 0; j < length - i; j++) {
			builder.append(s.charAt(length - 1 - j));
		}
		builder.append(s);
		return builder.toString();
	}

	public boolean isPalidrome(String string) {
		int length = string.length();
		for (int i = 0; i < length / 2; i++) {
			if (string.charAt(i) != string.charAt(length - 1 - i)) {
				return false;
			}
		}
		return true;
	}
}
